package 简单算法;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: 胡成
 * @Version: 0.0.1V
 * @Date: 2019-05-21
 * @Description: 给定一个整数数组A。
 * 定义B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]， 计算B的时候请不要使用除法。请输出B。
 * 样例
 * 样例 1
 * 输入: A = [1, 2, 3]
 * 输出: [6, 3, 2]
 * 解析：B[0] = A[1] * A[2] = 6; B[1] = A[0] * A[2] = 3; B[2] = A[0] * A[1] = 2
 * 样例 2
 * 输入: A = [2, 4, 6]
 * 输出: [24, 12, 8]
 **/
public class 数组剔除元素后的乘积 {
    public static void main(String[] args) {
        数组剔除元素后的乘积 s = new 数组剔除元素后的乘积();
        List<Integer> nums = new ArrayList<>();
        nums.add(2);
        nums.add(1);
        nums.add(3);
        nums.add(4);
        System.out.println(s.productExcludeItself(nums));
    }

    public List<Long> productExcludeItself(List<Integer> nums) {
        // write your code here
        List<Long> ans = new ArrayList<>();
//        查看差别
//                [2,1,3,4]
//        输出
//                [12,24,8,6]
//        期望答案
//                [12,24,8,6]

        // 0  --> 4*3*1  //从右计算 nums[3] * nums[2] * nums[1]
        // 1  --> 2*3*4  //从左计算 nums[0] * nums[0+2] * nums[0+3]
        // 2  --> 2*1*4  //从左计算 nums[0] * nums[0+1] * nums[0+3]
        // 3  --> 2*1*3  //从左计算 nums[0] * nums[0+1] * nums[0+2]

        long left = 1;
        ans.add(1L);
        for (int i = 1; i < nums.size(); i++) {
            left = left * (long) nums.get(i - 1);
            ans.add(left);
        }

        System.out.println(ans);
        long right = 1;
        for (int i = nums.size() - 2; i >= 0; i--) {
            right = right * nums.get(i + 1);
            ans.set(i,ans.get(i) * right);
        }
        return ans;
    }

}
